Vasilis Syrgkanis
Abstract:
In many settings agents participate in multiple different auctions that are not necessarily implemented simultaneously. Future opportunities affect strategic considerations of the players in each auction. Motivated by this consideration, we study a setting of a market of buyers and sellers, where sellers hold item auctions sequentially. We examine both the complete and incomplete information version of the setting.
For the complete information setting we prove that if sellers hold sequential first price auctions then for unit-demand bidders (matching market) every subgame perfect equilibrium achieves at least half of the optimal social welfare, while for submodular bidders or when second price auctions are used, the social welfare can be arbitrarily worse than the optimal. We also show that a subgame perfect equilibrium in pure strategies always exists. For the incomplete information setting we prove that for the case of unit-demand bidders any Bayesian equilibrium achieves at least 1/3 of the optimal welfare.
This talk is based on papers in SODA '12 and EC'12, joint with Renato Paes Leme and Eva Tardos